package com.lun.swordtowardoffer2.c14;

public class MinCostClimbingStairs {

	//方法一：递归代码
	public int minCostClimbingStairs1(int[] cost) {
		int len = cost.length;
		return Math.min(helper1(cost, len - 2), helper1(cost, len - 1));
	}

	private int helper1(int[] cost, int i) {
		if (i < 2) {
			return cost[i];
		}
		return Math.min(helper1(cost, i - 2), helper1(cost, i - 1)) + cost[i];
	}

	//方法二：使用缓存的递归代码
	public int minCostClimbingStairs2(int[] cost) {
		int len = cost.length;
		int[] dp = new int[len];
		helper2(cost, len - 1, dp);
		return Math.min(dp[len - 2], dp[len - 1]);

	}

	private void helper2(int[] cost, int i, int[] dp) {
		if (i < 2) {
			dp[i] = cost[i];
		} else if (dp[i] == 0) {
			helper2(cost, i - 2, dp);
			helper2(cost, i - 1, dp);
			dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i];

		}
	}

	//方法三：空间复杂度为O(n)的迭代代码
	public int minCostClimbingStairs3(int[] cost) {
		int len = cost.length;
		int[] dp = new int[len];
		dp[0] = cost[0];
		dp[1] = cost[1];
		for (int i = 2; i < len; i++) {
			dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
		}
		return Math.min(dp[len - 2], dp[len - 1]);
	}

	//方法四：空间复杂度为O(1)的迭代代码
	public int minCostClimbingStairs4(int[] cost) {
		int len = cost.length;
		int[] dp = {cost[0], cost[1]};
		for (int i = 2; i < len; i++) {
			dp[i & 1] = Math.min(dp[0], dp[1]) + cost[i];
		}
		return Math.min(dp[0], dp[1]);
	}

}
